class Solution(object):
    def smallestDistancePair(self, nums, k):
        nums.sort()
        n = len(nums)
        diff = [nums[i + 1] - nums[i] for i in range(n - 1)]
        prefix = [0] * n
        for i in range(1, n):
            prefix[i] += prefix[i - 1] + diff[i - 1]

        def search(value):
            left = 0
            right = 1
            c = 0
            max_value = 0
            while right < n:
                while left < right and prefix[right] - prefix[left] > value:
                    left += 1
                c += right - left
                max_value = max(max_value, prefix[right] - prefix[left])
                right += 1
            if c >= k:
                return max_value
            else:
                return -1

        left = min(diff)
        right = prefix[-1] - prefix[0]
        while left < right:
            mid = (right + left) // 2
            max_value = search(mid)
            if max_value == -1:
                left = mid + 1
            else:
                right = mid

        return left


data = Solution()
nums = [9, 10, 7, 10, 6, 1, 5, 4, 9, 8]
k = 18
print(data.smallestDistancePair(nums, k))
